package problem674;

//674.回文子串
//https://leetcode.cn/problems/palindromic-substrings/description/

class Solution {
    public int countSubstrings(String _s) {
        char[] s = _s.toCharArray();
        int n = _s.length();
        boolean[][] dp = new boolean[n][n];
        int sum = 0;
        for(int i = n-1; i>=0; i--) {
            for(int j = i; j<n; j++) {
                if(i == j) dp[i][j] = true;
                else if(s[i] == s[j] && i+1 == j) dp[i][j] = true;
                else if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
                if(dp[i][j]) sum++;
            }
        }
        return sum;
    }
}

/*

dp[i][j]:以第i到j个字符串能否组成回文子串
从左下方向右上方填表
需要从下到上, 从左往右填表
*/